package niuke;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * NC41 最长无重复子数组
 * 题目
 * 题解(205)
 * 讨论(345)
 * 排行
 * 中等  通过率：32.29%  时间限制：2秒  空间限制：256M
 * 知识点
 * 哈希
 * 双指针
 * 数组
 * 描述
 * 给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
 * 子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
 *
 * 数据范围：0\le arr.length \le 10^60≤arr.length≤10
 * 6
 *  ，0 < arr[i] \le 10^50<arr[i]≤10
 * 5
 *
 * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
 * 示例1
 * 输入：
 * [2,3,4,5]
 * 复制
 * 返回值：
 * 4
 * 复制
 * 说明：
 * [2,3,4,5]是最长子数组
 * 示例2
 * 输入：
 * [2,2,3,4,3]
 * 复制
 * 返回值：
 * 3
 * 复制
 * 说明：
 * [2,3,4]是最长子数组
 * 示例3
 * 输入：
 * [9]
 * 复制
 * 返回值：
 * 1
 * 复制
 * 示例4
 * 输入：
 * [1,2,3,1,2,3,2,2]
 * 复制
 * 返回值：
 * 3
 * 复制
 * 说明：
 * 最长子数组为[1,2,3]
 * 示例5
 * 输入：
 * [2,2,3,4,8,99,3]
 * 复制
 * 返回值：
 * 5
 * 复制
 * 说明：
 * 最长子数组为[2,3,4,8,99]
 * */
public class LongestUnduplicatedSubArray {
    public static void main(String[] args) {
        int[] pam = {1,2,3,4,1,5,6,7,8,1};
//        int[] pam = {2,3,4,5};
//        int[] pam = {1,2,3,5,1,6,7,1};
//        int[] pam = {1,2,4,1,6,5,1,1};
        LongestUnduplicatedSubArray longestUnduplicatedSubArray = new LongestUnduplicatedSubArray();
        int result = longestUnduplicatedSubArray.maxLength2(pam);
        System.out.println(result);
    }

    /**
     * 执行正确，但是超时
     * 时间复杂度 O（n 平方）
     * 空间复杂度 O (n 平方)
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        List<Map<Integer,Integer>> list = new ArrayList<>();
        int result = 0;
        //初始化
        for (int i = 0; i < arr.length; i++) {
            Map<Integer,Integer> tem = new HashMap<>();
            tem.put(arr[i],arr[i]);
            // 0 代表无重复，且连续，可以继续放
            tem.put(-1,0);
            list.add(tem);
        }
        //遍历
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (list.get(j).get(-1) == 0 && list.get(j).get(arr[i]) == null){
                    list.get(j).put(arr[i],arr[i]);
                }else {
                    list.get(j).put(-1,1);
                }
            }
        }

        for (int i = 0; i< list.size(); i++){
            if (result < (list.get(i).size()-1)) result = list.get(i).size()-1;
        }

        return result;
    }

    /**
     * 我们可以利用双指针模拟一个滑动窗口。初始化该窗口为(left, right]。
     * 所以left从-1开始。窗口不断往右扩大。因为我们要的是无重复子数组，因此，遇到有重复的数字，在窗口左侧进行缩小。
     * 在每次滑动时，对窗口的大小进行比较，保留最大的长度。
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength2 (int[] arr) {
        if (arr.length < 2){
            return arr.length;
        }
        Map<Integer, Integer> windows = new HashMap<>(); //存的方式：<value,index>
        int left = -1;
        int result = 0;
        for (int right = 0; right < arr.length; right++) {
            if (windows.containsKey(arr[right])) { //有重复
                left = Math.max(left, windows.get(arr[right]));
            }
            windows.put(arr[right],right);
            result = Math.max(result,right - left );
        }
        return result;
    }
}
